การเพิ่มประสิทธิภาพแบบโควาเวกซ์: พื้นฐานการประมาณค่าด้วยระยะทาง

ลองนึกภาพว่าคุณเป็นช่างตัดเสื้อผ้าที่พยายามให้เสื้อสูทมาตรฐาน (ช่วงของ $A$) เข้ากับร่างกายของลูกค้าที่มีสัดส่วนเฉพาะตัว (เวกเตอร์ $b$) ไม่ว่าคุณจะปรับแขนหรือเอว (สัมประสิทธิ์ $x$) อย่างไร เสื้อก็จะไม่มีทางเข้ากันได้สมบูรณ์แบบ คุณกำลังมองหาความสมดุลที่ดีที่สุด— การประมาณค่าด้วยระยะทาง ซึ่งลดแรงดึงดูดหรือค่าคงที่ที่เกิดขึ้นทุกจุดเย็บ

กรอบทางคณิตศาสตร์

เป้าหมายหลักคือการหาเวกเตอร์ $x \in \mathbb{R}^n$ ซึ่งการรวมเชิงเส้น $Ax = x_1a_1 + \dots + x_na_n$ ใกล้เคียงกับ $b$ มากที่สุด ซึ่งมักเรียกว่า การถดถอยของ $b$ ไปยังตัวแปรอธิบาย (คอลัมน์ของ $A$)

เราเน้นที่เวกเตอร์ผลต่าง $r = Ax - b$ ในทางปฏิบัติ เราสมมติว่าเป็นระบบที่มีจำนวนสมการมากกว่าจำนวนตัวแปร ระบบเกินจำนวน โดยที่ $m > n$ ทำไม? เพราะเมื่อ $m = n$ และ $A$ เป็นแมทริกซ์ที่ไม่เป็นเอกลักษณ์ จุดที่เหมาะสมที่สุดก็คือ $A^{-1}b$ ซึ่งทำให้เกิดข้อผิดพลาดเป็นศูนย์ ซึ่งเป็นกรณีที่เรียบง่ายสำหรับการเพิ่มประสิทธิภาพ

🎯 หลักการสำคัญ

ปัญหาการประมาณค่าด้วยระยะทาง (6.1) เป็น ปัญหาเชิงโค้ง และมีความแน่นอนว่าจะ แก้ไขได้มีอยู่เสมออย่างน้อยหนึ่งคำตอบที่เหมาะสมที่สุด $\hat{x}$ ซึ่งลดระยะห่างระหว่างเป้าหมายกับพื้นที่ที่สามารถบรรลุได้

รูปแบบที่พบบ่อย

ขึ้นอยู่กับประเภทของข้อผิดพลาดที่เราต้องการลงโทษ จึงเลือกใช้กฎระยะทางที่แตกต่างกัน:

1. การหาค่าต่ำสุด (กฎระยะทาง $\ell_2$)

เป็นแนวทางที่พบบ่อยที่สุด มันลดผลรวมของกำลังสองของค่าคงที่: $\|Ax - b\|_2^2$ มันไวต่อค่าเบี่ยงเบนที่มาก แต่ให้คำตอบเชิงวิเคราะห์ผ่านสมการปกติ

2. เชบีเชฟ / ต่ำสุด-สูงสุด ($\ell_\infty$ กฎระยะทาง)

ลดค่า สูงสุด ค่าคงที่สัมบูรณ์ $\max_i |r_i|$ ใช้เมื่อการวัดค่าทุกครั้งต้องอยู่ในขอบเขตที่แน่นอน สามารถแก้ไขได้ผ่านโปรแกรมเชิงเส้น (LP) ดังนี้:

หาค่าต่ำสุด $t$
ภายใต้เงื่อนไข $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

3. ผลรวมของค่าคงที่สัมบูรณ์ ($\ell_1$ กฎระยะทาง)

ลดผลรวม $\sum |r_i|$ วิธีนี้ทนทานต่อค่าเบี่ยงเบนที่มาก เพราะไม่ยกกำลังสองค่าผิดพลาด มันยังแก้ไขได้โดยใช้โปรแกรมเชิงเส้น (LP):

หาค่าต่ำสุด $\mathbf{1}^T t$
ภายใต้เงื่อนไข $-t \preceq Ax - b \preceq t$

บริบทของการประมาณค่า

ในหลายสาขาวิศวกรรม เราสมมติว่าสถานะจริง $x$ ถูกบดบังด้วยเสียงรบกวน: $y = Ax + v$ เป้าหมายของเราคือการหาค่าประมาณ $\hat{x} = \text{argmin}_z \|Az - y\|$ โดยการเลือกกฎระยะทาง เราแท้จริงแล้วกำลังสมมติเกี่ยวกับการแจกแจงทางสถิติของเสียงรบกวน $v$

\text{หาค่าต่ำสุด } \|u - b\| \text{ภายใต้เงื่อนไข } u \in \mathcal{A} \quad (\text{โดยที่ } \mathcal{A} = \text{ช่วงของ } A)

คำถามที่ 1

ในบริบทของการประมาณค่าด้วยระยะทาง ทำไมเราจึงสมมติว่า $m > n$ โดยทั่วไป?

เพราะหาก $m = n$ คำตอบจะเป็น $x = A^{-1}b$ ที่มีค่าคงที่เป็นศูนย์ ซึ่งเป็นกรณีที่เรียบง่าย

เพื่อให้มั่นใจว่าปัญหายังคงไม่เป็นเชิงโค้ง

เพราะกฎระยะทาง $\ell_1$ ต้องการตัวแปรมากกว่าข้อจำกัดเพื่อให้แก้ไขได้

เพื่อให้มั่นใจว่าเมทริกซ์ $A$ จะเป็นเมทริกซ์ที่ไม่สามารถหาค่ากลับได้เสมอ

คำถามที่ 2

รูปแบบโปรแกรมเชิงเส้น (LP) ใดที่ถูกต้องในการแสดงปัญหาการประมาณค่าเชบีเชฟ (ต่ำสุด-สูงสุด)?

หาค่าต่ำสุด $t$ ภายใต้เงื่อนไข $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

หาค่าต่ำสุด $\mathbf{1}^T t$ ภายใต้เงื่อนไข $-t \preceq Ax - b \preceq t$

หาค่าต่ำสุด $\|Ax - b\|_2$ ภายใต้เงื่อนไข $x \succeq 0$

หาค่าต่ำสุด $t$ ภายใต้เงื่อนไข $Ax - b = t$

คำถามที่ 3

คุณกำลังปรับค่าเซนเซอร์ และต้องการให้แน่ใจว่าการวัดค่าใด ๆ ไม่เคยเบี่ยงเบนจากโมเดลเกินจำนวนคงที่ คุณควรใช้กฎระยะทางใด?

$L^\infty$ (เชบีเชฟ)

$L^1$ (ผลรวมของค่าคงที่สัมบูรณ์)

$L^2$ (การหาค่าต่ำสุด)

กฎระยะทางฟรอเบเนียส

คำถามที่ 4

อะไรเป็นจริงเกี่ยวกับความสามารถในการแก้ปัญหาการประมาณค่าด้วยระยะทาง (6.1)?

มีความแน่นอนว่าสามารถแก้ไขได้และเป็นเชิงโค้ง

มีความแน่นอนว่าสามารถแก้ไขได้ก็ต่อเมื่อเมทริกซ์ $A$ เป็นสมมาตร

มันไม่เป็นเชิงโค้งหากใช้กฎระยะทาง $L^1$

ไม่มีคำตอบหากระบบเป็นระบบที่มีจำนวนสมการมากกว่าจำนวนตัวแปร

คำถามที่ 5

ในนิพจน์ $y = Ax + v$ หาก $v$ แทนเสียงรบกวนแบบลาปลาซีน (ซึ่งมีหางหนาแน่นกว่าเสียงรบกวนแบบเกาส์เชียน) กฎระยะทางใดที่มีความทนทานทางสถิติมากกว่า?

$L^1$ (ผลรวมของค่าคงที่สัมบูรณ์)

$L^2$ (การหาค่าต่ำสุด)

$L^\infty$ (เชบีเชฟ)

กฎระยะทางเทียม $L^0$

ภารกิจ: การออกแบบการปรับค่าเซนเซอร์

การจำลองเชิงปฏิบัติ

วิศวกรหุ่นยนต์กำลังปรับค่าเครื่องวัดเร่งแบบ 3 แกน โดยใช้การวัดตัวอย่าง 100 ค่า ($m=100$) เพื่อกำหนดค่าคงที่การปรับค่าทางกายภาพ 3 ค่า ($n=3$) ให้ $A$ เป็นเมทริกซ์ขนาด $100 \times 3$ ของข้อมูลการสังเกต และ $b$ เป็นค่าอ้างอิงเป้าหมาย

คำถาม 1

หากวิศวกรสงสัยว่าการวัด 5% เป็น 'ข้อผิดพลาด' (ค่าเบี่ยงเบนที่มากเกิดจากสัญญาณรบกวนไฟฟ้า) พวกเขาควรเลือกเป้าหมายตามกฎระยะทางใด และรูปแบบข้อจำกัดของโปรแกรมเชิงเส้น (LP) คืออะไร?

คำตอบ: ใช้ กฎระยะทาง $L^1$ (ผลรวมของค่าคงที่สัมบูรณ์) รูปแบบโปรแกรมเชิงเส้น (LP) คือ:
หาค่าต่ำสุด $\mathbf{1}^T t$
ภายใต้เงื่อนไข: $-t \preceq Ax - b \preceq t$
นี่เป็นที่ต้องการเพราะ $L^1$ ไม่ยกกำลังสองค่าคงที่ ทำให้ไวต่อค่าเบี่ยงเบนที่มากน้อยกว่า $L^2$

คำถาม 2

ถ้าเปลี่ยนจาก $L^2$ เป็น $L^\infty$ คำตอบที่เหมาะสมที่สุดจะเป็นอย่างไร?

คำตอบ: คำตอบ $L^2$ (การหาค่าต่ำสุด) พยายามลดค่าเฉลี่ยของผลรวมกำลังสองของข้อผิดพลาดทั้ง 100 เซนเซอร์ คำตอบ $L^\infty$ (เชบีเชฟ) เน้นลดเฉพาะ ค่าผิดพลาดสูงสุดเพียงค่าเดียวซึ่งมักจะทำให้ข้อผิดพลาดสม่ำเสมอทั้งหมดในเซนเซอร์ แต่ผลรวมของค่าผิดพลาดกำลังสองจะสูงขึ้น